package com.hedl.practice.StudyAlgorithm.heap_sorting;

import java.util.Arrays;

public class HeapSorting {

    /**
     * 首先判断数组是否为空或长度为0，如果是则直接返回。
     * 初始化变量len为数组的长度。
     * 建堆。使用for循环，循环条件为i从len/2-1到0。在循环中，调用heapify方法将以i为根节点的子树调整成大根堆。
     * 排序。使用for循环，循环条件为i从len-1到0。在循环中，交换arr[0]和arr[i]的值，将arr[i]放到已排序的序列末尾。然后调用heapify方法将剩余元素构成新的大根堆。
     * 重复步骤4，直到排序完成。
     * 在heapify方法中，初始化变量largest为i，表示以i为根节点的子树中最大元素的下标。初始化左子节点下标left为2i+1，右子节点下标right为2i+2。
     * 如果left小于len且arr[left]大于arr[largest]，则更新largest为left。
     * 如果right小于len且arr[right]大于arr[largest]，则更新largest为right。
     * 如果largest不等于i，说明以i为根节点的子树中存在比arr[i]大的元素，将arr[i]与arr[largest]交换位置。
     * 重复步骤7到9，直到heapify完成。
     * @param arr
     */
    public void heapSort(Integer[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        int len = arr.length;
        // 建堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(arr, len, i);
        }
        // 排序
        for (int i = len - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    private void heapify(Integer[] arr, int len, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, len, largest);
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {13,54,12,56,44,32,87,93,57,29,39,79,55,32,23,56};
        new HeapSorting().heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
